Recursive decoding techniques are considered for Reed-Muller (RM) codes ofgrowing length $n$ and fixed order $r.$ An algorithm is designed that hascomplexity of order $n\log n$ and corrects most error patterns of weight up to$n(1/2-\varepsilon)$ given that $\varepsilon$ exceeds $n^{-1/2^{r}}.$ Thisimproves the asymptotic bounds known for decoding RM codes with nonexponentialcomplexity.
展开▼
机译：对于增长长度为$ n $和固定阶为$ r的Reed-Muller（RM）码，考虑使用递归解码技术。设计了一种算法，该算法具有阶数为$ n \ log n $的复杂度，并且校正了权重最大为$ n的大多数错误模式。假设$ \ varepsilon $超过$ n ^ {-1/2 ^ {r}}。（1 / 2- \ varepsilon）$。这将改善已知的以非指数复杂度解码RM代码的渐近边界。
展开▼
